package com.example.demo.zaqizabatest.sortalgorithm;

/**
 * @ClassName HeapSort1
 * @Author lys4134
 * @Date 2021/12/30 11:12:56
 * @Description HeapSort1
 * @Version 1.0
 **/
public class HeapSort1 {

    public int[] sortArray(int[] nums) {
        sort(nums);
        return nums;
    }

    public static void sort(int[] nums) {
        // 这里需要 - 1 ，因为要访问最右边界的话，需要-1
        int n = nums.length - 1;

        // 从第一个非叶子节点开始，让倒数第二层开始依次往前保证自己是个大顶堆
        // 最终到了根节点后，就全是大顶堆了
        // 此时的大顶堆，不能保证左右孩子有序
        // 数学角度考虑，完全二叉树放到数组后，各层之间的数学关系，下面也是如此
        // 这里实际上是 k = nums.length / 2 - 1
        for (int k = (n - 1) / 2; k >= 0; k--) {
            sink(nums, k, n);
        }

        // 最大的放在末尾依次向前排序
        while (n > 0) {
            exch(nums, 0, n--); // 把目前最大的数放到数组末尾, 最大的沉下去了，肯定是升序数组啊
            sink(nums, 0, n); // 从头部开始，到已经放过的数的前一个，恢复大顶堆，再次找到最大的那个数
        }
        // 上面的循环， 实际上是这个意思
//        for (int i = 0; i < n; i++) {
//            exch(nums, 0, n - i);
//            sink(nums, 0, n - i - 1);
//        }

    }


    // n表示数组最右位的下标，防越界
    public static void sink(int[] a, int k, int n) {
        while (true) {
            int j = 2 * (k + 1) - 1;
            // 如果 j > n 说明当前节点是倒数第一层，所以退出循环。
            if (j > n) {
                break;
            }
            // 保证后面比较且交换的是更大的那个子节点。
            // 并且从这段代码可以猜测，大顶堆从 0 开始建的话，任意节点的子节点都是 2x 和 2x+1
            if (j < n && less(a, j, j + 1)) {
                j++;
            }
            // 大于 大的那个子节点，就可以调出循环，结束sink()，不用沉了。
            if (!less(a, k, j)) {
                break;
            }
            // 如果比子节点中 大的 那个 小，则交换大的到当前位置
            exch(a, k, j);
            // 更新标记游标，再次循环计算是否需要和子节点发生交换
            k = j;
        }

    }




    public static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static boolean less(int[] a, int i, int j) {
        return a[i] < a[j];
    }
	/*
	 * // 仅排序的话，用不着他们 // 并且并不知道这里的数学关系调整对了没
        public static void sink(int[] a, int k) {
            while (2 * k + 1 <= a.length) {
                int j = 2 * k + 2;
                if (j < a.length && less(a, j, j + 1)) j++;
                if (!less(a, k, j)) break; // k >= j ， 则会触发break
	        exch(a, k, j);
                k = j;
            }
        }
	public static void swim(int[] a, int k) {
            while (k > 0 && less(a,k / 2, k)) {
	        exch(a, k / 2 + 2, k);
                k = k / 2 + 2;
            }
        }
	 */

}
